Vigenère Cipher
   HOME

TheInfoList



OR:

The Vigenère cipher () is a method of
encrypting In cryptography, encryption is the process of Code, encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can ...
alphabetic An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syllab ...
text by using a series of interwoven Caesar ciphers, based on the letters of a keyword. It employs a form of
polyalphabetic substitution A polyalphabetic cipher substitution, using multiple substitution alphabets. The Vigenère cipher is probably the best-known example of a polyalphabetic cipher, though it is a simplified special case. The Enigma machine is more complex but is sti ...
. First described by
Giovan Battista Bellaso Giovan Battista Bellaso (Brescia 1505–...) was an Italian cryptologist. The Vigenère cipher is named after Blaise de Vigenère, although Giovan Battista Bellaso had invented it before Vigenère described his autokey cipher. Biography Bellaso ...
in 1553, the cipher is easy to understand and implement, but it resisted all attempts to break it until 1863, three centuries later. This earned it the description le chiffrage indéchiffrable ( French for 'the indecipherable cipher'). Many people have tried to implement encryption schemes that are essentially Vigenère ciphers. In 1863,
Friedrich Kasiski Major Friedrich Wilhelm Kasiski (29 November 1805 – 22 May 1881) was a German infantry officer, cryptographer and archeologist. Kasiski was born in Schlochau, Kingdom of Prussia (now Człuchów, Poland). Military service Kasiski enlisted in ...
was the first to publish a general method of deciphering Vigenère ciphers. In the 19th century, the scheme was misattributed to
Blaise de Vigenère Blaise de Vigenère (5 April 1523 – 19 February 1596) () was a French diplomat, cryptographer, translator and alchemist. Biography Vigenère was born into a respectable family in the village of Saint-Pourçain. His mother, Jean, arrang ...
(1523–1596) and so acquired its present name.


History

The very first well-documented description of a polyalphabetic cipher was by
Leon Battista Alberti Leon Battista Alberti (; 14 February 1404 – 25 April 1472) was an Italian Renaissance humanist author, artist, architect, poet, priest, linguist, philosopher, and cryptographer; he epitomised the nature of those identified now as polymaths. H ...
around 1467 and used a metal
cipher disk A cipher disk is an enciphering and deciphering tool developed in 1470 by the Italian architect and author Leon Battista Alberti. He constructed a device, (eponymously called the Alberti cipher disk) consisting of two concentric circular plate ...
to switch between cipher alphabets. Alberti's system only switched alphabets after several words, and switches were indicated by writing the letter of the corresponding alphabet in the ciphertext. Later, Johannes Trithemius, in his work ''Polygraphiae'' (which was completed in manuscript form in 1508 but first published in 1518), invented the
tabula recta In cryptography, the ''tabula recta'' (from Latin ''tabula rēcta'') is a square table of alphabets, each row of which is made by shifting the previous one to the left. The term was invented by the German author and monk Johannes TrithemiusSal ...
, a critical component of the Vigenère cipher. The
Trithemius cipher In cryptography, the ''tabula recta'' (from Latin '' tabula rēcta'') is a square table of alphabets, each row of which is made by shifting the previous one to the left. The term was invented by the German author and monk Johannes TrithemiusS ...
, however, provided a progressive, rather rigid and predictable system for switching between cipher alphabets.In a separate manuscript that Trithemius called the ''Clavis Polygraphiae'' (The Key to the Polygraphia), he explained (among other things) how to encipher messages by using a polyalphabetic cipher and how to decipher such messages. The ''Clavis Polygraphiae'' was not always included in the original 1518 printed copies, and even when it was included, it wasn't always inserted in the same location in the ''Polygraphiae''. From (Gamer, 2015), p. 129: ''"Eine eigene Stellung innerhalb … in den Ausführungen zu Buch VI."'' (The ''Clavis'' occupies a peculiar place within the text that's been passed down only in print. Trithemius alludes several times in other places to the existence of a ''Clavis Polygraphiae'' as a separate work, contemporaneous with the manuscript of 1508. However, we know only the edition that is bound with the printed version, which was sporadically adapted to changes during printing, as often as not – as, for example, in the case of the shifted chapter on alphanumeric number notation. The ''Clavis'' didn't accompany this relocation: the explanations of the representations of numbers remained in the remarks on Book VI.)
The ''Clavis'' explains how to encipher and decipher messages by using polyalphabetic ciphers. In Trithemius' examples, he decoded a message by using two Vignere tables – one in which the letters are in normal alphabetical order and the other in which the letters are in reversed order (see (Gamer, 2015), p. 128). Fro
(Trithemius, 1518), pp. 19–20

Original Latin text: ''"In primis tabulam descripsimus rectam, alphabeta quatuor & viginti continentem, per cuius intelligentiam tot poterunt alphabeta componi, quot stellae numerantur in firmamento caeli. Quot enim in ipsa tabula sunt grammata, totiens consurgunt ex arte decies centena milia per ordinem alphabeta. Post haec tabulam distribuimus aversam, quae totiens consurget in aliam, quotiens literam mutaveris a capite primam. Est autem litera prima in tabula recta b, & in aversa z. In quarum locum quotiens reposueris quamlibet aliam variatam totiens invenies tabulam per omnia novam, & ita usque ad infinitum. Deinde primam tabulam rectam expandimus, unicuique literae transpositae nigrae illam quam repraesentat ad caput eius cum minio collocantes, ut modum scribendi faciliorem lectori praeberemus. Est autem modus iste scribendi, ut in primo alphabeto nigro, capias occultae sententiae literam unam, de secundo aliam, de tertio tertiam, & sic consequenter usque ad finem. Quo cum perveneris, totiens ad ordinem primum redeundum memineris, quousque mentis tuae secretum mysterium occultando compleveris. Verum ut ordinem videas, ponamus exemplum. Hxpf gfbmcz fueib gmbt gxhsr ege rbd qopmauwu. wfxegk ak tnrqxyx. Huius mystici sermonis sententia est. Hunc caveto virum, quia malus est, fur, deceptor, mendax & iniquus. Cernis iam nunc lector quam mirabilem transpositionem literarum alphabeti haec tabula reddat, cum sit nemo qui sine noticia eius hoc valeat penetrare secretum. Exedit enim modus iste scribendi omnem transpositionem literarum communem, cum unaquaeque litera semper de una serie alphabeti mutetur in aliam. Ex tabula quoque aversa quam simili distributione per ordinem expandimus, pro introductione tale ponamus exemplum. Rdkt, stznyb, tevqz, fnzf, fdrgh, vfd. Cuius arcani sensus est talis, Hunc caveto virum, quia malus st Et nota quod sub exemplo tabulae recte iam posito seriem occultam a principio per totum eius deduximus, & deinceps continuando similiter per aversam, rursusque circulum facimus, ut cernis ad principium tabulae rectae."''
English translation: In the first llustration we have transcribed a regular table [i.e., ''tabula recta'', a table in which the letters of alphabet are listed in their normal order; se
(Trithemius, 1518), p. 471.
containing 24 alphabets [Note: Trithemius used alphabets containing only 24 letters by setting j=i and v=u.], by which knowledge they will be able to compose as many alphabets as stars are numbered in the firmament of heaven. For in the table itself there are as many letters as arise by [applying] skill – a million per alphabetical row. hat is, the letters in the table need not be listed in alphabetical order, so many enciphering tables can be created. After this, we arrange he alphabets inthe reverse table [i.e., ''tabula aversa'', a table in which the letters of the alphabet are listed in reverse order; se
(Trithemius, 1518), p. 472.
, which will arise in the other [reversed table] as many times as you will have changed [i.e., permuted] the first letter of the top [of the regular table]. And so the first letter in the regular table is b, and z in the reverse [table]. As often as you will have put in its place another changed able you will find a new table for everything, and so on indefinitely. hat is, again, many enciphering tables can be created. Next we explain the first regular table: it shows how it is assigning, to each transposed black letter, letterin red nk alongits .e., the table'stop order in order to show to the reader an easier way of writing .e., of deciphering messages And that is a way of writing so that in the first black alphabet .e., an alphabet printed in the table using black, not red, ink you will get one letter of the hidden sentence .e., the deciphered message from the second lack alphabet another eciphered letter from the third lack alphabet a third eciphered letter and thus accordingly until the end. You will have arrived there .e., at the endwhen you will have recalled returning many times to the first row, until you will have completed concealing the secret mystery of your thought. [That is, the message is deciphered by deciphering its first 24 letters by using the ''tabula recta'', then repeating the procedure by using the same ''tabula recta'' to decipher the next 24 letters of the message, and so on.] However, so that you [can] see the sequence [i.e., procedure], we present an example: ''Hxpf gfbmcz fueib gmbt gxhsr ege rbd qopmauwu wfxegk ak tnrqxyx.'' The meaning of this mystical sentence is: ''Hunc caveto virum, quia malus est, fur, deceptor, mendax et iniquus.'' (Beware of this man, who is bad, a thief, a deceiver, a liar, and unjust.) You already discern now, reader, how this table renders an astonishing transposition of the letters of the alphabet, because there is no one who, without acquaintance of this, can penetrate the secret. For that method of writing corrodes every transposition of common letters, because each and every letter of one sequence of the alphabet is always changed into another
etter Etter is a surname. Notable people with the surname include: *Albert Etter (born 1872), American horticulturist *Bill Etter (born 1950), American football quarterback *Bob Etter (born 1945), American football placekicker, bridge player, and profess ...
Likewise, we explain how o decipher a message by means of the sequence .e., the deciphering procedure from the reverse table with a similar arrangement
f letters F, or f, is the sixth letter in the Latin alphabet, used in the modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is ''ef'' (pronounced ), and the plural is ''efs''. His ...
as an introduction, we present such an example: ''Rdkt, stznyb, tevqz, fnzf, fdrgh, vfd.'' The secret meaning of which is such: ''Hunc caveto virum, quia malus st'' (Beware of this man, who is bad.) And note about the example of the regular table
hat was A hat is a head covering which is worn for various reasons, including protection against weather conditions, ceremonial reasons such as university graduation, religious reasons, safety, or as a fashion accessory. Hats which incorporate mecha ...
already presented .e., the example that began with ''Hxpf'' that we derived the secret series .e., the deciphered messagefrom the beginning through all of it .e., of the regular table and thereafter by continuing similarly by means of the reverse able and again we make a circle, so that you are looking at the beginning of the regular table. [That is, the message is deciphered by using the regular table, but if the message is longer than 24 characters, then the decipherment continues by using the reverse table, and if necessary, one continues to decipher by returning to the regular table – and so forth.]
In 1586 Blaise de Vigenère published a type of polyalphabetic cipher called an autokey cipher – because its key is based on the original plaintext – before the court of Henry III of France. The cipher now known as the Vigenère cipher, however, is that originally described by
Giovan Battista Bellaso Giovan Battista Bellaso (Brescia 1505–...) was an Italian cryptologist. The Vigenère cipher is named after Blaise de Vigenère, although Giovan Battista Bellaso had invented it before Vigenère described his autokey cipher. Biography Bellaso ...
in his 1553 book ''La cifra del Sig. Giovan Battista Bellaso''. He built upon the tabula recta of Trithemius but added a repeating "countersign" (a Key (cryptography), key) to switch cipher alphabets every letter. Whereas Alberti and Trithemius used a fixed pattern of substitutions, Bellaso's scheme meant the pattern of substitutions could be easily changed, simply by selecting a new key. Keys were typically single words or short phrases, known to both parties in advance, or transmitted "out of band" along with the message. Bellaso's method thus required strong security for only the key. As it is relatively easy to secure a short key phrase, such as by a previous private conversation, Bellaso's system was considerably more secure. In the 19th century, the invention of Bellaso's cipher was misattributed to Vigenère. David Kahn, in his book, ''The Codebreakers'' lamented this misattribution, saying that history had "ignored this important contribution and instead named a regressive and elementary cipher for him igenèrethough he had nothing to do with it". The Vigenère cipher gained a reputation for being exceptionally strong. Noted author and mathematician Charles Lutwidge Dodgson (
Lewis Carroll Charles Lutwidge Dodgson (; 27 January 1832 – 14 January 1898), better known by his pen name Lewis Carroll, was an English author, poet and mathematician. His most notable works are ''Alice's Adventures in Wonderland'' (1865) and its sequel ...
) called the Vigenère cipher unbreakable in his 1868 piece "
The Alphabet Cipher Lewis Carroll published "The Alphabet-Cipher" in 1868, possibly in a children's magazine. It describes what is known as a Vigenère cipher, a well-known scheme in cryptography. While Carroll calls this cipher "unbreakable," Kasiski had already publ ...
" in a children's magazine. In 1917, ''
Scientific American ''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many famous scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it. In print since 1845, it i ...
'' described the Vigenère cipher as "impossible of translation". That reputation was not deserved.
Charles Babbage Charles Babbage (; 26 December 1791 – 18 October 1871) was an English polymath. A mathematician, philosopher, inventor and mechanical engineer, Babbage originated the concept of a digital programmable computer. Babbage is considered ...
is known to have broken a variant of the cipher as early as 1854 but did not publish his work. Kasiski entirely broke the cipher and published the technique in the 19th century, but even in the 16th century, some skilled cryptanalysts could occasionally break the cipher. The Vigenère cipher is simple enough to be a field cipher if it is used in conjunction with cipher disks. The
Confederate States of America The Confederate States of America (CSA), commonly referred to as the Confederate States or the Confederacy was an unrecognized breakaway republic in the Southern United States that existed from February 8, 1861, to May 9, 1865. The Confeder ...
, for example, used a brass cipher disk to implement the Vigenère cipher during the
American Civil War The American Civil War (April 12, 1861 – May 26, 1865; also known by other names) was a civil war in the United States. It was fought between the Union ("the North") and the Confederacy ("the South"), the latter formed by states th ...
. The Confederacy's messages were far from secret, and the Union regularly cracked its messages. Throughout the war, the Confederate leadership primarily relied upon three key phrases: "Manchester Bluff", "Complete Victory" and, as the war came to a close, "Come Retribution". A Vigenère cipher with a completely random (and non-reusable) key which is as long as the message becomes a
one-time pad In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is not smaller than the message being sent. In this technique, a plaintext is paired with a ran ...
, a theoretically unbreakable cipher.
Gilbert Vernam Gilbert Sandford Vernam (April 3, 1890 – February 7, 1960) was a Worcester Polytechnic Institute 1914 graduate and AT&T Bell Labs engineer who, in 1917, invented an additive polyalphabetic stream cipher and later co-invented an automated on ...
tried to repair the broken cipher (creating the Vernam–Vigenère cipher in 1918), but the technology he used was so cumbersome as to be impracticable.


Description

In a Caesar cipher, each letter of the alphabet is shifted along some number of places. For example, in a Caesar cipher of shift 3, a would become D, b would become E, y would become B and so on. The Vigenère cipher has several Caesar ciphers in sequence with different shift values. To encrypt, a table of alphabets can be used, termed a ''
tabula recta In cryptography, the ''tabula recta'' (from Latin ''tabula rēcta'') is a square table of alphabets, each row of which is made by shifting the previous one to the left. The term was invented by the German author and monk Johannes TrithemiusSal ...
'', ''Vigenère square'' or ''Vigenère table''. It has the alphabet written out 26 times in different rows, each alphabet shifted cyclically to the left compared to the previous alphabet, corresponding to the 26 possible Caesar ciphers. At different points in the encryption process, the cipher uses a different alphabet from one of the rows. The alphabet used at each point depends on a repeating keyword. For example, suppose that the
plaintext In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted. Overview With the advent of comp ...
to be encrypted is :attackatdawn. The person sending the message chooses a keyword and repeats it until it matches the length of the plaintext, for example, the keyword "LEMON": :LEMONLEMONLE Each row starts with a key letter. The rest of the row holds the letters A to Z (in shifted order). Although there are 26 key rows shown, a code will use only as many keys (different alphabets) as there are unique letters in the key string, here just 5 keys: . For successive letters of the message, successive letters of the key string will be taken and each message letter enciphered by using its corresponding key row. The next letter of the key is chosen, and that row is gone along to find the column heading that matches the message character. The letter at the intersection of ey-row, msg-colis the enciphered letter. For example, the first letter of the plaintext, a, is paired with L, the first letter of the key. Therefore, row A and column L of the Vigenère square are used, namely L. Similarly, for the second letter of the plaintext, the second letter of the key is used. The letter at row T and column E is X. The rest of the plaintext is enciphered in a similar fashion: Decryption is performed by going to the row in the table corresponding to the key, finding the position of the ciphertext letter in that row and then using the column's label as the plaintext. For example, in row L (from ''L''EMON), the ciphertext L appears in column A, so a is the first plaintext letter. Next, in row E (from L''E''MON), the ciphertext X is located in column T. Thus t is the second plaintext letter.


Algebraic description

Vigenère can also be described algebraically. If the letters AZ are taken to be the numbers 0–25 (A \,\widehat\, 0, B \,\widehat\, 1, etc.), and addition is performed modulo 26, Vigenère encryption E using the key K can be written as :C_i = E_K(M_i) = (M_i+K_i) \bmod 26 and decryption D using the key K as :M_i = D_K(C_i) = (C_i-K_i) \bmod 26, in which M = M_1 \dots M_n is the message, C = C_1 \dots C_n is the ciphertext and K = K_1 \dots K_n is the key obtained by repeating the keyword \lceil n / m \rceil times in which m is the keyword length. Thus, by using the previous example, to encrypt A \,\widehat\, 0 with key letter L \,\widehat\, 11 the calculation would result in 11 \,\widehat\, L. :11 = (0+11) \bmod 26 Therefore, to decrypt R \,\widehat\, 17 with key letter E \,\widehat\, 4, the calculation would result in 13 \,\widehat\, N. :13 = (17-4) \bmod 26 In general, if \Sigma is the alphabet of length \ell, and m is the length of key, Vigenère encryption and decryption can be written: :C_i = E_K(M_i) = (M_i+K_) \bmod \ell, :M_i = D_K(C_i) = (C_i-K_) \bmod \ell. M_i denotes the offset of the ''i''-th character of the plaintext M in the alphabet \Sigma. For example, by taking the 26 English characters as the alphabet \Sigma = (A,B,C,\ldots,X,Y,Z), the offset of A is 0, the offset of B is 1 etc. C_i and K_i are similar.


Cryptanalysis

The idea behind the Vigenère cipher, like all other polyalphabetic ciphers, is to disguise the plaintext
letter frequency Letter frequency is the number of times letters of the alphabet appear on average in written language. Letter frequency analysis dates back to the Arab mathematician Al-Kindi (c. 801–873 AD), who formally developed the method to break ...
to interfere with a straightforward application of
frequency analysis In cryptanalysis, frequency analysis (also known as counting letters) is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers. Frequency analysis is based on t ...
. For instance, if P is the most frequent letter in a ciphertext whose plaintext is in
English English usually refers to: * English language * English people English may also refer to: Peoples, culture, and language * ''English'', an adjective for something of, from, or related to England ** English national ide ...
, one might suspect that P corresponds to e since e is the most frequently used letter in English. However, by using the Vigenère cipher, e can be enciphered as different ciphertext letters at different points in the message, which defeats simple frequency analysis. The primary weakness of the Vigenère cipher is the repeating nature of its
key Key or The Key may refer to: Common meanings * Key (cryptography), a piece of information that controls the operation of a cryptography algorithm * Key (lock), device used to control access to places or facilities restricted by a lock * Key (map ...
. If a cryptanalyst correctly guesses the key's length ''n'', the cipher text can be treated as ''n'' interleaved Caesar ciphers, which can easily be broken individually. The key length may be discovered by brute force testing each possible value of ''n'', or
Kasiski examination In cryptanalysis, Kasiski examination (also referred to as Kasiski's test or Kasiski's method) is a method of attacking polyalphabetic substitution ciphers, such as the Vigenère cipher. It was first published by Friedrich Kasiski in 1863, but se ...
and the
Friedman test The Friedman test is a non-parametric statistical test developed by Milton Friedman. Similar to the parametric repeated measures ANOVA, it is used to detect differences in treatments across multiple test attempts. The procedure involves ranking ...
can help to determine the key length (see below: and ).


Kasiski examination

In 1863,
Friedrich Kasiski Major Friedrich Wilhelm Kasiski (29 November 1805 – 22 May 1881) was a German infantry officer, cryptographer and archeologist. Kasiski was born in Schlochau, Kingdom of Prussia (now Człuchów, Poland). Military service Kasiski enlisted in ...
was the first to publish a successful general attack on the Vigenère cipher. Earlier attacks relied on knowledge of the plaintext or the use of a recognizable word as a key. Kasiski's method had no such dependencies. Although Kasiski was the first to publish an account of the attack, it is clear that others had been aware of it. In 1854,
Charles Babbage Charles Babbage (; 26 December 1791 – 18 October 1871) was an English polymath. A mathematician, philosopher, inventor and mechanical engineer, Babbage originated the concept of a digital programmable computer. Babbage is considered ...
was goaded into breaking the Vigenère cipher when John Hall Brock Thwaites submitted a "new" cipher to the Journal of the Society of the Arts. When Babbage showed that Thwaites' cipher was essentially just another recreation of the Vigenère cipher, Thwaites presented a challenge to Babbage: given an original text (from Shakespeare's '' The Tempest'': Act 1, Scene 2) and its enciphered version, he was to find the key words that Thwaites had used to encipher the original text. Babbage soon found the key words: "two" and "combined". Babbage then enciphered the same passage from Shakespeare using different key words and challenged Thwaites to find Babbage's key words. Babbage never explained the method that he used. Studies of Babbage's notes reveal that he had used the method later published by Kasiski and suggest that he had been using the method as early as 1846. The
Kasiski examination In cryptanalysis, Kasiski examination (also referred to as Kasiski's test or Kasiski's method) is a method of attacking polyalphabetic substitution ciphers, such as the Vigenère cipher. It was first published by Friedrich Kasiski in 1863, but se ...
, also called the Kasiski test, takes advantage of the fact that repeated words are, by chance, sometimes encrypted using the same key letters, leading to repeated groups in the ciphertext. For example, consider the following encryption using the keyword ABCD: Key: ''ABCDAB''CDABCDABCD''ABCDAB''CDABCD Plaintext: ''crypto''isshortfor''crypto''graphy Ciphertext: ''CSASTP''KVSIQUTGQU''CSASTP''IUAQJB There is an easily noticed repetition in the ciphertext, and so the Kasiski test will be effective. The distance between the repetitions of CSASTP is 16. If it is assumed that the repeated segments represent the same plaintext segments, that implies that the key is 16, 8, 4, 2, or 1 characters long. (All
factors Factor, a Latin word meaning "who/which acts", may refer to: Commerce * Factor (agent), a person who acts for, notably a mercantile and colonial agent * Factor (Scotland), a person or firm managing a Scottish estate * Factors of production, suc ...
of the distance are possible key lengths; a key of length one is just a simple Caesar cipher, and its cryptanalysis is much easier.) Since key lengths 2 and 1 are unrealistically short, one needs to try only lengths 16, 8, and 4. Longer messages make the test more accurate because they usually contain more repeated ciphertext segments. The following ciphertext has two segments that are repeated: Ciphertext: ''VHVS''SP''QUCE''MRVBVBBB''VHVS''URQGIBDUGRNICJ''QUCE''RVUAXSSR The distance between the repetitions of VHVS is 18. If it is assumed that the repeated segments represent the same plaintext segments, that implies that the key is 18, 9, 6, 3, 2, or 1 characters long. The distance between the repetitions of QUCE is 30 characters. That means that the key length could be 30, 15, 10, 6, 5, 3, 2, or 1 characters long. By taking the intersection of those sets, one could safely conclude that the most likely key length is 6 since 3, 2, and 1 are unrealistically short.


Friedman test

The Friedman test (sometimes known as the kappa test) was invented during the 1920s by
William F. Friedman William Frederick Friedman (September 24, 1891 – November 12, 1969) was a US Army cryptographer who ran the research division of the Army's Signal Intelligence Service (SIS) in the 1930s, and parts of its follow-on services into the 1950s. ...
, who used the
index of coincidence In cryptography, coincidence counting is the technique (invented by William F. Friedman) of putting two texts side-by-side and counting the number of times that identical letters appear in the same position in both texts. This count, either as a r ...
, which measures the unevenness of the cipher letter frequencies to break the cipher. By knowing the probability \kappa_\text that any two randomly chosen source language letters are the same (around 0.067 for
case-insensitive In computers, case sensitivity defines whether uppercase and lowercase letters are treated as distinct (case-sensitive) or equivalent (case-insensitive). For instance, when users interested in learning about dogs search an e-book, "dog" and "Dog" a ...
English) and the probability of a coincidence for a uniform random selection from the alphabet \kappa_\text ( = 0.0385 for English), the key length can be estimated as the following: : \frac from the observed coincidence rate : \kappa_\text=\frac in which ''c'' is the size of the alphabet (26 for English), ''N'' is the length of the text and ''n''1 to ''n''''c'' are the observed ciphertext
letter frequencies Letter frequency is the number of times letters of the alphabet appear on average in written language. Letter frequency analysis dates back to the Arab mathematician Al-Kindi (c. 801–873 AD), who formally developed the method to break ...
, as integers. That is, however, only an approximation; its accuracy increases with the length of the text. It would, in practice, be necessary to try various key lengths that are close to the estimate. A better approach for repeating-key ciphers is to copy the ciphertext into rows of a matrix with as many columns as an assumed key length and then to compute the average
index of coincidence In cryptography, coincidence counting is the technique (invented by William F. Friedman) of putting two texts side-by-side and counting the number of times that identical letters appear in the same position in both texts. This count, either as a r ...
with each column considered separately. When that is done for each possible key length, the highest average index of coincidence then corresponds to the most-likely key length. Such tests may be supplemented by information from the Kasiski examination.


Frequency analysis

Once the length of the key is known, the ciphertext can be rewritten into that many columns, with each column corresponding to a single letter of the key. Each column consists of plaintext that has been encrypted by a single Caesar cipher. The Caesar key (shift) is just the letter of the Vigenère key that was used for that column. Using methods similar to those used to break the Caesar cipher, the letters in the ciphertext can be discovered. An improvement to the Kasiski examination, known as
Kerckhoffs Auguste Kerckhoffs (19 January 1835 – 9 August 1903) was a Dutch linguistics, linguist and cryptographer in the late 19th century. Biography Kerckhoffs was born in Nuth, the Netherlands, as Jean Guillaume Auguste Victor François Huber ...
' method, matches each column's letter frequencies to shifted plaintext frequencies to discover the key letter (Caesar shift) for that column. Once every letter in the key is known, all the cryptanalyst has to do is to decrypt the ciphertext and reveal the plaintext. Kerckhoffs' method is not applicable if the Vigenère table has been scrambled, rather than using normal alphabetic sequences, but Kasiski examination and coincidence tests can still be used to determine key length.


Key elimination

The Vigenère cipher, with normal alphabets, essentially uses modulo arithmetic, which is commutative. Therefore, if the key length is known (or guessed), subtracting the cipher text from itself, offset by the key length, will produce the plain text subtracted from itself, also offset by the key length. If any "probable word" in the plain text is known or can be guessed, its self-subtraction can be recognized, which allows recovery of the key by subtracting the known plaintext from the cipher text. Key elimination is especially useful against short messages. For example using LION as the key below: Then subtract the ciphertext from itself with a shift of the key length 4 for LION. Which is nearly equivalent to subtracting the plaintext from itself by the same shift. Which is algebraically represented for i \in , n - m/math> as: : \begin (C_i - C_) \bmod \ell &= (E_K(M_i) - E_K(M_)) \bmod \ell \\ &= ((M_i + K_) \bmod \ell - (M_ + K_) \bmod \ell) \bmod \ell \\ &= ((M_i + K_) - (M_ + K_)) \bmod \ell \\ &= (M_i + K_ - M_ - K_) \bmod \ell \\ &= (M_i - M_ + K_ - K_) \bmod \ell \\ &= (M_i - M_ + K_ - K_) \bmod \ell \\ &= (M_i - M_) \bmod \ell \\ \end In this example, the words brownfox are known. This result omaz corresponds with the 9th through 12th letters in the result of the larger examples above. The known section and its location is verified. Subtract brow from that range of the ciphertext. This produces the final result, the reveal of the key LION.


Variants


Running key

The running key variant of the Vigenère cipher was also considered unbreakable at one time. For the key, this version uses a block of text as long as the plaintext. Since the key is as long as the message, the Friedman and Kasiski tests no longer work, as the key is not repeated. If multiple keys are used, the effective key length is the least common multiple of the lengths of the individual keys. For example, using the two keys GO and CAT, whose lengths are 2 and 3, one obtains an effective key length of 6 (the least common multiple of 2 and 3). This can be understood as the point where both keys line up. Encrypting twice, first with the key GO and then with the key CAT is the same as encrypting once with a key produced by encrypting one key with the other. This is demonstrated by encrypting attackatdawn with IOZQGH, to produce the same ciphertext as in the original example. If key lengths are relatively prime, the effective key length grows exponentially as the individual key lengths are increased. For example, while the effective length of keys 10, 12, and 15 characters is only 60, that of keys of 8, 11, and 15 characters is 1320. If this effective key length is longer than the ciphertext, it achieves the same immunity to the Friedman and Kasiski tests as the running key variant. If one uses a key that is truly random, is at least as long as the encrypted message, and is used only once, the Vigenère cipher is theoretically unbreakable. However, in that case, the key, not the cipher, provides cryptographic strength, and such systems are properly referred to collectively as
one-time pad In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is not smaller than the message being sent. In this technique, a plaintext is paired with a ran ...
systems, irrespective of the ciphers employed.


Variant Beaufort

A simple variant is to encrypt by using the Vigenère decryption method and to decrypt by using Vigenère encryption. That method is sometimes referred to as "Variant Beaufort". It is different from the
Beaufort cipher The Beaufort cipher, created by Sir Francis Beaufort, is a substitution cipher similar to the Vigenère cipher, with a slightly modified enciphering mechanism and tableau. Its most famous application was in a rotor-based cipher machine, the Hag ...
, created by Francis Beaufort, which is similar to Vigenère but uses a slightly modified enciphering mechanism and tableau. The Beaufort cipher is a
reciprocal cipher Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between t ...
.


Gronsfeld cipher

Despite the Vigenère cipher's apparent strength, it never became widely used throughout Europe. The Gronsfeld cipher is a variant created by Count Gronsfeld (Josse Maximilaan van
Gronsveld Gronsveld ( li, Groêselt or Groéselt) is a village in the Dutch province of Limburg. It is part of the municipality of Eijsden-Margraten and situated southeast of the municipality of Maastricht, to which it is bordering. Gronsveld was a sepa ...
né van Bronckhorst); it is identical to the Vigenère cipher except that it uses just 10 different cipher alphabets, corresponding to the digits 0 to 9). A Gronsfeld key of 0123 is the same as a Vigenere key of ABCD. The Gronsfeld cipher is strengthened because its key is not a word, but it is weakened because it has just 10 cipher alphabets. It is Gronsfeld's cipher that became widely used throughout Germany and Europe, despite its weaknesses.


Vigenèreʼs autokey cipher

Vigenère actually invented a stronger cipher, an autokey cipher. The name "Vigenère cipher" became associated with a simpler polyalphabetic cipher instead. In fact, the two ciphers were often confused, and both were sometimes called ''le chiffre indéchiffrable''. Babbage actually broke the much-stronger autokey cipher, but Kasiski is generally credited with the first published solution to the fixed-key polyalphabetic ciphers.


See also

*
Roger Frontenac Roger Frontenac was a French navy officer and a scholar of Nostradamus' prophecies. He proposed an interpretation system for the text of ''Les Propheties'', based upon a form of cryptography known as the Vigenère table. Biography Roger Fronte ...
(
Nostradamus Michel de Nostredame (December 1503 – July 1566), usually Latinised as Nostradamus, was a French astrologer, apothecary, physician, and reputed seer, who is best known for his book ''Les Prophéties'' (published in 1555), a collection o ...
quatrain decryptor, 1950)
A Simple Vigenere Cipher for Excel VBA
Provides VBA code to use the Excel worksheet for Vigenere cipher encryption and decryption.


References


Citations


Sources

* * * *


Notes


External links

;Articles
History of the cipher from Cryptologia

Basic Cryptanalysis
at H2G2

including an explanation and derivation of the Friedman Test {{DEFAULTSORT:Vigenere Cipher Classical ciphers Stream ciphers de:Polyalphabetische Substitution#Vigen.C3.A8re-Verschl.C3.BCsselung